Various techniques are available to improve dynamic prediction of conditional computer instructions during execution. Prediction of conditional instructions is often used to better select future instructions whose execution may be dependent on the outcome of the conditional instructions, or to accelerate execution of those future instructions. Among prediction techniques, branch prediction and predication are sometimes used. Branch prediction is often used when conditional instructions in a program are compiled to lead to two possible branching locations (or “targets”). Branch target prediction, used in branch predictors, may also be used to identify a nonconditional jump target. In this technique, a history of branch choices taken before execution of the current conditional instruction may be examined to predict that one branch or the other should be scheduled for execution.
In predication, sets of instructions associated with a conditional instruction are compiled to be associated with a predicate value, such as a Boolean value, and this predicate is typically evaluated separately. In this technique, two sets of instructions (based on the value of the conditional) are separately evaluated and results from those instructions whose associated predicate value was not the result after evaluation may be thrown away or discarded. Predicate values may themselves be predicted, such as by operating a prediction technique using a history of predicate values as input.
Current systems which use these techniques, and in particular systems which organize instructions into instruction blocks, suffer from difficulties, however. The use of branch prediction alone, both when predicting either results of branches or jump targets, fails to provide a facility for contemporaneous prediction of control instructions within blocks of instructions, which often takes the form of predication. Predication, conversely, is not suited to jumps across block boundaries. Existing predication techniques, which may serialize predicate predications, suffer from additional overhead as instructions with later predicates are forced to wait for earlier-occurring predicates. In systems which attempt to combine the techniques, the use of branch prediction and predicate prediction requires multiple data structures and introduces substantial execution overhead. Furthermore, in current systems, branches are predicted between blocks without knowledge of intervening predicates; these branches, which are predicted with a more sparse instruction history, can suffer from poor prediction accuracy.